1. Field of the Invention
This invention relates to the rendering of graphic images on computer displays. More specifically, this invention relates to the rendering of anti-aliased polygons on computer graphic displays.
2. Art Background
In the scan conversion process of a polygon, the polygon, which is defined by the coordinates of its vertices, is converted to a raster image. The outline or edges of the polygon are first determined and the pixels between the polygon edges are then filled. The vertices of the polygon are translated into the display coordinate space and a line scan conversion algorithm is used to determine the lines between vertices which form the edges of the polygon. The line scan conversion algorithm computes the coordinates of the pixels which lie closest to the line between vertices on a two-dimensional raster grid. An example is Bresenham's line algorithm (for information on Bresenham's line algorithm see: Foley and Van Dam, Fundamentals of Interactive Computer Graphics, (Addison-Wesley Publishing, 1984) pages 433-436). However, the lines do not always coincide or "line up" with pixel locations. Although the closest pixel is chosen, the resulting line contains the undesirable alias effect. This undesirable effect also is carried into the polygon rendering process.
In an attempt to smooth out the edges of a polygon during the polygon rendering process, Pitteway and Watkinson modified Bresenham's algorithm to determine a partial coverage value for pixels which form the edge of a polygon. The modification involved adding to Bresenham's error term the quantity (1-m), where m is the slope. The result is that the error term is a measure of the area of the pixel inside the polygon (for further information on the Pitteway/Watkinson algorithm see Foley and Van Dam, Fundamentals of Interactive Computer Graphics, (Addison-Wesley Publishing, 1984), pages 460-463). Using the Pitteway/Watkinson algorithm, a pixel intensity is generated which is equal to the pixel area covered multiplied by the color or intensity of the polygon at that pixel (since a shaded polygon may result in a different intensity or color).
The coverage value computed using the Pitteway/Watkinson algorithm is the area between the line of the polygon and the major axis. If the polygon lies toward the major axis, i.e., between the line being drawn and the major axis, the coverage value can be used directly. If the polygon lies toward the minor axis, the desired coverage value equals the difference between the value of one and the Pitteway/Watkins coverage value determined. Because the Pitteway and Watkinson algorithm can only address a single line, the algorithm cannot handle thin polygons whose thickness may be less than one pixel and which may reside within the area of a single pixel, or vertices which meet within the area of a single pixel. In addition, since the algorithm touches one pixel per major axis increment, some pixels are partially covered by a polygon are treated as though they are uncovered. Furthermore, the Pitteway/Watkinson algorithm only performs a simple averaging process and does not extend direclty to different convolution or weighted averaging functions.
Another approach to rendering a polygon employs a sub-pixel mask which indicates the locations of coverage within the pixels. For example, a sub-pixel mask may provide a 16-bit pattern on a 4.times.4 grid of coverage for a polygon on a pixel. The mask represents coverage of combination of 16 sub-pixel areas plus full coverage and no coverage which provides for 256 different combinations of sub-pixel masks. To accommodate horizontal and vertical edges lying on integer pixel boundaries, the look-up table indices access a 5.times.5 array. This is illustrated by FIGS. 1a, 1b and 1c. The mask obtained from the table is a 4.times.4 array and is composed of bits where a value of zero indicates that the polygon does not cover the sub-pixel and a value of 1 indicates that it does. To use the sub-pixel mask, the polygon vertices are quantized to sub-pixel values after passing through any geometric manipulations. To calculate the indices for mask look-up the sign of the edge of the slope must be provided. This determines the integer x coordinate of the pixel which is adjacent to the current pixel in the direction of the slope. By convention, horizontal edges are rendered left to right so the adjacent pixel is always to the right. Vertical edges require the additional knowledge of whether they are left or right polygon edges to determine adjacent pixels. Referring to FIG. 1a, when the adjacent pixel's x value is subtracted from the current x value of the edge of the current pixel and the result is multiplied by the number of sub-pixels in x (4 for the present example) the following results are determined:
0=0 * 4; PA0 1=0.25 * 4; PA0 2=0.50 * 4; PA0 3=0.75 * 4; PA0 4=1 * 4
These values become the x index into a sub-pixel identifying matrix.
FIG. 1b illustrates the xy index and FIG. 1c depicts the sub-pixel identifying index. The same calculation performed for x is performed for the y values of the edge. The calculations to determine the y indices are simplified by the fact that the polygon is rendered a scan line at a time in the increasing y direction. The x and y indices give us sub-pixel number. (e.g. 0 through 24) of the entry index of the pixel. Sub-pixel masks are designed to allow the entry index to be within the pixel as well as on a pixel boundary. Identical procedures are performed for the exit sub-pixel. The exit sub-pixel is calculated as soon as an adjacent pixel or scan line has been intercepted or when the edges ends (if it ends within the current pixel).
Once the two sub-pixel indices for the entry and exit sub-pixels are determined, the mask is obtained from the look-up table and is either used as is or complemented depending upon the edge code which indicates which side of the edge is an inside edge and which is an outside edge. The mask for multiple edges of a single polygon within a pixel are combined depending upon a vertex code; the masks are logically ORed together if the vertex represents two edges whose inside angle is greater than 180.degree. (concave) and logically ANDed together if the inside angle is less than or equal to 180.degree. (convex) The sub pixel masks themselves may be determined empirically or according to a predetermined algorithm so long as consistent algorithms are used to generate all the masks. Memory may be saved by providing only half of the possible combinations of edge crossings in as much as the other half may be obtained by complementing the bit pattern based upon the knowledge of the relationship of the edges in a mask to the inside/outside of the polygon.
Once the desired partial coverage pixels on the edge of a polygon have been computed, the internal pixels between the polygon edge pixels on a span on a scan line must be filled. Filling a span on a scan line requires determination of the right most edge pixel on the left edge of a polygon and left most edge pixel on the next right edge of the polygon. Once determined, the pixels between these edge pixels are filled. FIG. 2a illustrates why it is necessary to determine the first and last fill pixels in a span since simply using the extreme edge pixels of the polygon on a span would result in adjacent edge pixels being entirely painted as opposed to partially painted i.e. "color* coverage" for edge pixels which are partially covered and simply "color" for fill pixels which are fully painted. FIG. 2b shows an example where only two pixels in the span should be entirely filled since there are five left edge pixels (including one vertex) and two right edge pixels.
For a single polygon there may be several spans on an individual scan line which must be filled (See Foley and Van Dam, Fundamentals of Interactive Computer Graphics, p. 456, for a description of rendering a polygon). Determining the individual spans on a particular scan line involves rendering all edges of the polygon on that scan line and determining the first and last pixels in a span to be completely filled. Upon determination of these first and last fill pixels, an X order sort is performed on their position in the scan line and individual spans are then filled in a left to right order.
Once the energy or coverage for each pixel of a polygon is determined, the polygon image may then be composited into the background. Compositing is a technique wherein the pixels of the polygon are blended into the background in order to have as smooth a transition as possible between the polygon and the background. In one method for compositing, a separate component or channel, referred to as the alpha ".alpha." channel, is used to identify the extent of coverage of an element at a pixel. See Porter & Duff, "Compositing Digital Images", Computer Graphics, Vol. 18, No. 3, (July 1984), In order to place the element over an arbitrary background, a mixing factor is required at each pixel to control the linear interpolation of the foreground and background colors. This information is encoded into the .alpha. channel, which at a value of zero indicates no coverage and at a value of 1 means full coverage with fractions corresponding to partial coverage. The elements of an image (pixel) are then composited into the background according to the following compositing equation: EQU c.sub.t =.alpha..sub.a *c.sub.a +(1-.alpha..sub.a)*.alpha..sub.b *c.sub.b EQU .alpha..sub.t =.alpha..sub.a +(1-.alpha..sub.a)*.alpha..sub.b
where c.sub.a is the color of the pixel of the polygon, c.sub.b is the color of the background object, c.sub.t is the color of the pixel upon compositing, .alpha..sub.a is the value of the partial coverage of the pixel of the polygon, .alpha..sub.b is a partial coverage of the background pixel and .alpha..sub.t is the composited .alpha. value.
In one implementation of the .alpha. channel the .alpha. channel retains only a single .alpha. value per pixel which is proportional to the partial coverage at a pixel by the polygon. No information associated with the orientation or shape of the partial coverage is retained. In addition, if the number of polygon edges intersecting a pixel is greater than 1, the .alpha. value becomes a composite .alpha. value, and the actual number of intersecting polygons is unknown. These compositing equations are equally applied to all pixels of the polygon. Therefore, if the polygon ranges in depth, the pixels of the polygon will be rendered the same regardles of depth. Furthermore, the pixel color computed via the compositing equation is heavily dependent upon the rendering sequence of the polygons which overlap at a particular pixel. The closer the rendering sequence is to the actual depth order of the polygons, the more accurate is the computed color value to the desired color value. U.S Pat. No. 4,748,572 describes a mechanism in which the polygons to be rendered are sorted in depth order prior to compositing. However, the sorting process is quite time consuming, requires several processing passes and slows down the polygon rendering process considerably.
The error which arises when rendering intersecting polygons and which varies according to the depth order of the polygons is illustrated by the example of FIGS. 3a and 3b. FIG. 3a shows a pixel within which three polygons a, b, and c intersect. Each pixel within a polygon has a depth value associated with it identified as the z value and an .alpha. value indicative of the extent of coverage at the pixel. FIG. 3b shows the resulting color and .alpha. values which have been computed for each polygon for all possible depth orders for .alpha.a equal to one-half, .alpha.b equal to one-half and .alpha.c equal to one-half. FIG. 3b shows that in 4 out of 6 cases considered, cases 1, 2, 4 and 6, the contributions to the final pixel color from the three intersecting polygons are dependent upon the depth order. The error that arises as a result of this is referred to as the depth order dependence error.
FIG. 4 illustrates two cases of polygons a, b and c, having, .alpha.a equal to one-half, .alpha.b equal to one-quarter and .alpha.c equal to one. The sequence of rendering is c, b, a. It should be noted that when .alpha. obtains the value of one, it always remains at the value of one regardless of subsequent compositing with other polygons. FIG. 4 verifies this to be true irrespective of depth order. In addition, in the second case, there is no contribution to the final color from polygon "a" despite polygon a being in front of polygon c and having an .alpha. value equal to one-half. However, because the z value is updated after the computation of the color to a value of z=zb (at the second step), and the .alpha. values is equal to one, there is insufficient information to conclude anything other that polygon a is hidden by a polygon completely covering the pixel (even though the other polygon is actually in front of the polygon having an .alpha. value of 1).